package main

import (
	"errors"
	"fmt"
	"os"
)

/*
1、介绍
(1)有些程序员也把栈称为堆栈，即栈和堆栈是同一个概念
(2)栈的英文为stack
(3)栈是一个先进后出的有序列表
(4)栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(top)，另一端为固定的一端，称为栈底(Bottom)
(5)根据堆栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除
2、栈的应用场景
(1)子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。
(2)处理递归调用：和子程序的调用类似，只是除了存储下一个指令的地址外，也将参数、区域变量等数据存入堆栈中
(3)表达式的转换与求值
(4)二叉树的遍历
(5)图的深度优先搜索法
3、需求
请输入一个表达式
计算式：[7*2*2-5+1-5+3-3]点击计算
问：计算机底层是如何运算得到结果的？计算机接收到的就是一个字符串
*/
//使用数组来模拟一个栈的使用
type Stack struct {
	MaxTop int   //表示栈最大可以存放多少个数
	Top    int   //表示栈顶，因为栈顶固定，因此我们直接使用Top
	arr    []int //数组模拟栈
}

//入栈
func (this *Stack) Push(val int) (err error) {
	//先判断栈是否满了
	if this.Top == this.MaxTop-1 {
		fmt.Println("stack full")
		return errors.New("stack full")
	}
	this.Top++
	//放入数据
	this.arr[this.Top] = val
	fmt.Println("入栈成功")
	return
}

//出栈
func (this *Stack) Pop() (val int, err error) {
	//判断栈是否为空
	if this.Top == -1 {
		fmt.Println("stack empty")
		return 0, errors.New("stack empty")
	}
	//先取值，再this.Top--
	val = this.arr[this.Top]
	this.Top--
	return val, nil
}

//遍历栈，注意需要从栈顶开始遍历
func (this *Stack) List() {
	//先判断栈是否为空
	if this.Top == -1 {
		fmt.Println("stack empty")
		return
	}
	fmt.Println("栈的情况如下：")
	for i := this.Top; i >= 0; i-- {
		fmt.Printf("arr[%d]=%d\n", i, this.arr[i])
	}
}
func main() {
	stack := &Stack{
		Top: -1, //当栈顶为-1，表示栈为空
	}
	var key string
	var val int
	var MaxTop int
	for {
		fmt.Println("1输入cre构建栈的大小")
		fmt.Println("2输入add进行入栈")
		fmt.Println("3输入pop进行出栈")
		fmt.Println("4输入show显示栈")
		fmt.Println("5输入exit退出")
		fmt.Scanln(&key)
		switch key {
		case "cre":
			fmt.Println("输入大小:")
			fmt.Scanln(&MaxTop)
			stack.arr = make([]int, MaxTop, 2*MaxTop)
			stack.MaxTop = MaxTop
			fmt.Println("构建成功")
		case "add":
			fmt.Println("输入入栈的数据：")
			fmt.Scanln(&val)
			stack.Push(val)
			// fmt.Println("入栈成功")
		case "pop":
			val, _ := stack.Pop()
			fmt.Println("出栈val=", val)
		case "show":
			stack.List()
		case "exit":
			os.Exit(0)
		}
	}
}
